// 模板
#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<cstring>
using namespace std;
const int N=510;//这里太大会爆
int g[N][N];//稠密图用邻接矩阵(点少边多)注意看n和m的数据范围
int n,m;
int dijkstra(){
    unordered_set<int>s;
    unordered_map<int,int>dist;//保存每个点到终点的距离
    dist[1]=0;
    for(int i=2;i<=n;i++){
        dist[i]=0x3f3f3f3f;
    }
    //循环n次 遍历n个点
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!s.count(j)&&(t==-1||dist[j]<dist[t]))
                t=j;//保证了t 一定不再集合里 并且是集合外距离最小的 y总牛逼
        }//因为大循环 n次保证了t肯定不为-1
        s.insert(t);
        for(int j=1;j<=n;j++){
            dist[j]=min(dist[j],dist[t]+g[t][j]);//如果g[t][j]没有路径 不会溢出为负数
        }//0x3f3f3f3f 实现了 无穷大+d=无穷大
    }
    return dist[n]==0x3f3f3f3f?-1:dist[n];
}
int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);//初始化为无穷大
    while(m--){
        int a,b,d;
        cin>>a>>b>>d;
        g[a][b]=min(g[a][b],d);//存在重边 保存最短的即可
    }
    cout<<dijkstra();
    return 0;
}


// 不再s里距离home的距离最小的点 一定是它到home的最短距离，因为不会有别的点到它比当前的路径更短了。
// 用它到其他点的距离来更新其他点到home的距离
// 就执行n次就能确保得出结果
#include <iostream>
#include <unordered_map>
#include <utility>
#include <forward_list>
#include <climits>
#include <unordered_set>
using namespace std;
const int N = 100010;
forward_list<pair<int, int>> h[N];
unordered_map<int, int> d;
int n, m;
void add(int a, int b, int d)
{
    h[a].push_front({b, d});
}
int dijkstra()
{
    d[1] = 0;
    for (int i = 2; i <= n; i++)
        d[i] = INT_MAX;
    unordered_set<int> s;
    for (int i = 1; i <= n; i++)
    {
        //寻找可以确定最短距离的点
        int t = INT_MAX, dt = INT_MAX;
        for (int i = 1; i <= n; i++)
        {
            if (s.count(i))
                continue;
            if (d[i] < dt)
            {
                dt = d[i], t = i;
            }
        }
        if (t == INT_MAX)
            continue;
        s.insert(t);
        //用它到其他点的距离来更新其他点到home的距离
        for (auto p : h[t])
        {
            int x = p.first;
            d[x] = min(d[x], d[t] + p.second);
        }
    }
    return d[n] == INT_MAX ? -1 : d[n];
}
int main()
{
    cin >> n >> m;
    while (m--)
    {
        int a, b, x;
        cin >> a >> b >> x;
        add(a, b, x);
    }
    cout << dijkstra();
    return 0;
}